11.5 Complexity

133

where minimization is over all possible histories of ss and c Subscript upper H Baseline left parenthesis s right parenthesiscH(s) is the number of

components in the history. The production history upper H left parenthesis s right parenthesisH(s) is defined as the parsing of

ss into its mm components (words):

H (s) = s(1, h1)s(h1 + 1, h2) · · · s(hm−1 + 1, hm) .

(11.29)

German c left parenthesis s right parenthesisc(s) is thus the least possible number of steps in whichss can be generated according

to the given rules of production.

In order to go beyond purely internal qualities (i.e., correlations) of the string, it

will be useful to introduce some additional quantities, such as the joint algorithmic

complexity upper K left parenthesis s comma t right parenthesisK(s, t), the length of the smallest program required to print out two

strings ss and tt:

K(s, t) ≈ K(t, s) ≲K(s) + K(t) ;

(11.30)

the mutual algorithmic information

K(s : t) = K(s) + K(t) − K(s, t)

(11.31)

(which reflects the ability of a string to share information with another string); con-

ditional algorithmic information (or conditional complexity)

K(s|t) = K(s, t) − K(t)

(11.32)

(i.e., the length of the smallest program that can compute ss from tt); and algorithmic

information distance

D(s, t) = K(s, t) + K(t|s)

(11.33)

(the reader may verify that this measure fulfils the usual requirements for a distance).

Adami and Cerf have emphasized that randomness and complexity only exist with

respect to a specific, defined, environment ee (i.e., context). Consider the conditional

complexity upper K left parenthesis s vertical bar e right parenthesisK(s|e). The smallest program for computing ss from ee will only contain

elements unrelated to ee, since if they were related, they could be obtained (i.e.,

deduced) fromee with a program tending to size zero. Hence,upper K left parenthesis s vertical bar e right parenthesisK(s|e) quantifies those

elements inss that are random (with respect toee). ¹³ In principle, we can now use the

mutual algorithmic information defined by Eq. (11.31) to determine

K(s : e) = Kmax − K(s|e) ,

(11.34)

which represents the number of meaningful elements in string ss, although it might

not be practically possible to compute upper K left parenthesis s vertical bar e right parenthesisK(s|e) unless one is aware of the coding

scheme whereby some of ee is encapsulated in ss. A possible way of overcoming this

difficulty is opened where there exist multiple copies of a sequence that have adapted

independently to ee. It may then reasonably be assumed that the coding elements are

13 If there is no environment, then all strings have the maximum complexity,upper K Subscript normal m normal a normal xKmax.